package com.agile.leetcode.array.sort;

import java.util.Arrays;

/**
 * @Author ChenZhangKun
 * @Date 2020/9/9 16:46
 */
@SuppressWarnings("all")
public class RadixSort {
    public static void main(String[] args) {
        int[] array={1,2,6,4,84,8,0,78,13};
        int[] ints = radixSort(array);
        System.out.println(Arrays.toString(ints));
    }
    public static int[] radixSort(int[] array){
        // 找出最大的数
        int maxValue=Integer.MIN_VALUE;
        for (int i : array) {
            if (i>maxValue){
                maxValue=i;
            }
        }
        // 得到长度
        int length=(maxValue+"").length();
        // 定义二维数组
        int[][] bucket=new int[10][array.length];
        int[] bucketElementCount=new int[10];
        // 循环
        //
        int m=0;
        for (int i = 1; i <= length; i++) {
            m=(int)Math.pow(10,i-1);
            // 循环
            for (int j = 0; j < array.length; j++) {
                // 得到末尾数
                int digitOfElement=array[j]/m%10;
                bucket[digitOfElement][bucketElementCount[digitOfElement]]=array[j];
                bucketElementCount[digitOfElement]++;
            }
            int index=0;
            for (int i1 = 0; i1 < bucket.length; i1++) {
                if (bucketElementCount[i1]!=0){
                    for (int i2 = 0; i2 < bucketElementCount[i1]; i2++) {
                        array[index]=bucket[i1][i2];
                        index++;
                    }
                }
                bucketElementCount[i1]=0;
            }

        }
        return array;
    }
}
